The present invention deals with the area of encryption, decryption, re-encryption, permutation, and blinding of messages. Encryption takes a cleartext message and produces an encrypted message. Decryption takes an encrypted message and produces its corresponding cleartext message. Re-encryption takes an encrypted message and produces another encryption of the same message. Blinding may include the operations of encryption or reencryption and permutation which is later defined.
It is known in the prior art to take a message and turn it into an encrypted message using a first user's public key. The first user upon receiving the encrypted message can then decrypt it, to reveal the original message, using the first user's secret key. The first user's public key is as the name implies, available to the public so that others can send messages to the first user. However, the first user's secret key is not available. The public key is associated with a one-way function, i.e. once the message is encrypted it cannot be decrypted without the secret key even though the public key and the encryption algorithms are known.
El Gamal encryption is known in the art. This encryption takes a message m as an input; chooses a random value "r", and produces an outputs a=m*y.sup.r modulo p; b=g.sup.r modulo p. For El Gamal decryption c=a/b.sup.x modulo p; and the output c is the message m. For El Gamal re-encryption the input is (a,b), a random value r2 is chosen, a2=a*y.sup.r2 modulo p, b2=b*g.sup.r2 modulo p are calculated, and the output is (a2, b2). (a2, b2) and (a, b) decrypt to the same message "m" when all encryption is removed. In the above y=g.sup.x modulo p is the public key and x is the secret key. The variables g, x, and p and other system parameters are picked according to methods known to a person skilled in the art.
The present invention also refers to the area of permutation. An example of permutation is as follows. Three votes are received in the following order: "yes", "yes", "no". The votes are randomly permuted, that is reordered in some random fashion to produce for example the following order: "no", "yes", "yes". The votes are the same, i.e. two "yes"es and one "no", however by permuting them, which particular voter voted what cannot be determined. This is only true (that you cannot tell who voted what) as long as you don't know the permutation used. If the votes were first encrypted, then both permuted and re-encrypted then it is not possible to determine what input item produced what output item.
In mix networks, which are generally known, the concepts of encryption, decryption, and permutation are used together. A mix network takes a vector of values as input, and outputs a permuted or reordered list of function evaluations (typically decryptions) of the input items, without revealing the relationship between the input and output values. Mix networks are particularly useful for elections.
Prior art mix networks do not provide adequate privacy or robustness in an efficient manner. The term "Privacy" is used herein to mean providing for example a voter with privacy from others and from the entity or entities providing the mix, from discovering how he voted. The term "Robustness" is used herein to mean providing the ability to make sure that the final results were correctly calculated, even if some entities actively cheated. Efficiency is provided by utilizing a low amount of communication, storage, and computation.
There are two types of schemes already known as follows:
The first type, disclosed by Pedersen, are schemes with two or more processors where an input is processed by secret keys held by the processors, and some fixed number (set by the protocol designer) of processors have to cooperate. The scheme can be robust. It only decrypts one item at a time. If it decrypts more than that, the relationship between input and output messages is known, and therefore, there is no privacy. This first type is shown in FIG. 1.
The second type are schemes as above, but where there is privacy, obtained by using permutation, but there is no robustness. The second type is shown in FIG. 2, by David Chaum, Syverson, et al. and Gulcu et al., as known by those skilled in the art.
Neither of these schemes is well suited for elections, as either privacy or robustness is given up. Likewise, there are many other applications, such as web commerce schemes, where both privacy and robustness is required, and a solution based on either of the above two approaches.
In a more recent scheme, Ogata, Kurosawa, Sako, and Takatani disclose a mix network for decryption that has both privacy and robustness, but which is not efficient, as disclosed in "Fault tolerant anonymous channel," W. Ogata, K. Kurosawa, K. Sako, and K. Takatani, Proceedings of Information and Communications Security '97, pages 440-444. Their method is based on the well-known method of cut-and-choose, as can be appreciated by a person skilled in the art. In their scheme, each processor (or server) permutes and re-encrypts each message, and then permutes and re-encrypts again such permuted and re-encrypted message. Then this server is required to "open up" one of the two transactions. That means that it will reveal exactly how it performed one of the consecutive permutations and one of the consecutive re-encryptions. Which one is determined by the other servers. This process is repeated serveral times. If it is repeated k times then the probability that a processor will cheat and not be detected is 1/2**k (1/2k). For example, for k=3, the chances are 1/2**3=1/8. To gain a high degree of robustness, a large number of repetitions is required. Each processor has to engage in the above protocol. Since cut-and-choose is not efficient, neither is the resulting mix network for decryption.